template <class T>
class DSU
{
    int n;
    vector<T> p, sz;

public:
    DSU(T _n) : n(_n), sz(_n + 10, 1)
    {
        init(n);
    };
    void init(int n)
    {
        p.resize(n + 10);
        std::iota(p.begin(), p.end(), 0);
    }
    int find(int x)
    {
        return x == p[x] ? p[x] : p[x] = find(p[x]);
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
    int size(int x)
    {
        return sz[find(x)];
    }
};
